10038. Веселые прыжки

Последовательность из n > 0 целых чисел содержит веселые прыжки, если разности между соседними элементами пробегают все значения от 1 до n – 1.

Вход. Каждая строка начинается с числа n £ 3000, за которым следует последовательность из n целых чисел.

Выход. Для каждого теста вывести сообщение “Jolly” или “Not jolly” в зависимости от того, содержит ли входная последовательность веселые прыжки.

Пример входа

4 1 4 2 3
5 1 4 2 -1 6

Пример выхода

Jolly
Not jolly

РЕШЕНИЕ

обработка массива

Анализ алгоритма

Заведем массив used, который будет хранить информацию о разности соседних элементов: used[i] = 1, если в последовательности встретились соседние элементы с разницей i и used[i] = 0 иначе. Читаем последовательность, заполняем массив used. Далее проверяем, все ли разности от 1 до n – 1 встретились в последовательности и выводим результат.

Пример

В первом тесте последовательность состоит из 4 чисел, абсолютные значения соседних разностей соответственно равны: 3, 2, 1. То есть встречаются все возможные разности от 1 до 3. Последовательность содержит веселые прыжки и на выход следует вывести сообщение “Jolly”.

Реализация алгоритма

Для каждого теста читаем последовательность из n чисел. Для каждой соседней пары чисел a и b устанавливаем used[abs(a – b)] = 1.

while(scanf("%d",&n) == 1)

{

scanf("%d",&a);

memset(used,0,sizeof(used));

for(i = 0; i < n - 1; i++)

{

scanf("%d",&b);

used[abs(a - b)] = 1;

a = b;

}

Проверяем, все ли возможные разности между соседними элементами от 1 до n – 1 встретились. Для этого необходимо чтобы used[i] = 1, 1 £ i £ n – 1. Если для некоторого i из указанного интервала used[i] = 0, то устанавливаем flag = 1 (изначально инициализируем его нулем) и завершаем дальнейшую проверку.

flag = 0;

for(i = 1; i <= n - 1; i++)

if (!used[i]) {flag = 1; break;}

В зависимости от значения переменной flag выводим результат.

if(flag) printf("Not jolly\n"); else printf("Jolly\n");

}